[POJ 2723] Get Luffy Out

原题链接:POJ 2723 Get Luffy Out
题目大意:一共有nn对钥匙和mm个门,每个门上有两把锁,只要开了其中一把就可以往下一层.锁是按顺序给出的,也必须按顺序开.其次,每对钥匙如果用了其中一个,另外一个就不能用.一开始你在第00层,门在两层之间,问你最多能开多少扇门.
注意:钥匙只有在配对的另一个用了之后才不能用,一个钥匙本身是可以多次开门的

数据范围:
1n2101 \leq n \leq 2^{10}
1m2111 \leq m \leq 2^{11}

把门看做物品的话,可以发现每扇门都是必须要开的,并且有一个二元关系:即必须在两个锁之间开一个.由此可以想到使用2SAT2-SAT解决这个问题.不过由于题目问的是最多开多少个门,所以答案不是简单的建图再直接输出.简朴的暴力思想就是枚举每一扇门,但是可以发现由于门都是必须连续开的,也就是说开多少扇门是有单调性的,进而可以二分确定.

私以为网上看到的题解大部分没说明二分的判据和建图过程,这是非常要不得的,某些题解虽然过了,不过感觉有二分区间上的问题,可能要加一减一之类的操作,很怪.
考虑二分框架:每次判断midmid个门能不能过掉,开始先把[0,mid1][0,mid - 1]midmid个门建出来,再通过2SAT2-SAT判断是否是合法的,如果是合法的区间右移,由于midmid也可能是答案,所以l=midl=mid,反之,r=mid1r=mid-1,因为midmid必然不是答案,让r=mid1r=mid-1之后ll可以一直往前推到rr,因此可以覆盖所有情况.实际的代码框架见下:
注意建图过程是在checkcheck里的.

int l = 0,r = m;
while(l < r)
{
    int mid = l + r + 1 >> 1;
    if(check(mid))	l = mid;
    else r = mid - 1;
}

之后考虑建图,2SAT2-SAT建图的套路就是找一个选择和另外一个必须的选择.对于一个门来说,因为他必须要选一个,考虑以下两种情况:
①在用了左边的钥匙之后,左边钥匙配对的那个就不能用了,这是题目给的限制条件.这里得考虑把他变成一个必须条件:逆向考虑就可以了.假如说我选了左边钥匙的配对的那一把,则我不能再选左边那把钥匙了,我只能选右边那个门对应的钥匙.转换一下就是,如果我选了左边钥匙的配对钥匙,则我必须选择右边的那扇门,因为我左边的钥匙因为选了配对钥匙的原因被损坏了.这就是一个必须关系.
另外一个关系对称的来就行了,如果我选了右边钥匙的配对钥匙,则右边钥匙必不能选,我只能选左边的,因此就是右边钥匙的配对钥匙去连左边的钥匙.
具体建图的内容可以看代码,因为这个东西不太好描述,看代码建图还是直接一点.
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e5+7,M = 1e5+7;
int time_stamp,dfn[N],low[N];
int n,m;
int edge[M],succ[M],ver[N],idx;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,siz[N];
int op[N],p[N],q[N];
void add(int u,int v)
{
	edge[idx] = v;
	succ[idx] = ver[u];
	ver[u] = idx++;
}
void tarjan(int u)
{
	dfn[u] = low[u] = ++time_stamp;
	stk[++top] = u,in_stk[u] = 1;
	for(int i = ver[u];~i;i = succ[i])
	{
		int j = edge[i];
		if(!dfn[j])
		{
			tarjan(j);
			low[u] = min(low[u],low[j]);
		}
		else if(in_stk[j])	
			low[u] = min(low[u],dfn[j]);
	}
	if(dfn[u] == low[u])
	{
		int y;
		++scc_cnt;
		do
		{
			y = stk[top--];
			in_stk[y] = 0;
			id[y] = scc_cnt;
			siz[scc_cnt]++;
		}while(y != u);
	}
}
bool check(int lim)
{
	memset(ver,-1,sizeof ver);
	memset(dfn,0,sizeof dfn);
	idx = 0;top = 0;time_stamp = 0;scc_cnt = 0;
	memset(in_stk,0,sizeof in_stk);
	memset(low,0,sizeof low);
	for(int i = 0;i < lim;++i)
	{
		int u = p[i],v = q[i];
		add(op[u],v);
		add(op[v],u);
	}
	for(int i = 0;i < 2 * n;++i)
		if(!dfn[i])
			tarjan(i);
	for(int i = 0;i < n;++i)
		if(id[i] == id[op[i]])
			return 0;
	return 1;
}
int main()
{
	while(scanf("%d%d",&n,&m),n || m)
	{
		for(int i = 1;i <= n;++i)
		{
			int u,v;scanf("%d%d",&u,&v);
			op[u] = v;
			op[v] = u;
		}
		for(int i = 0;i < m;++i)	scanf("%d%d",&p[i],&q[i]);
		int l = 0,r = m;
		while(l < r)
		{
			int mid = l + r + 1 >> 1;
			if(check(mid))	l = mid;
			else r = mid - 1;
		}
		printf("%d\n",l);
	}
    return 0;
}